package leetcode.周赛.第275场;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2022/1/9 13:42
 * @description：https://leetcode-cn.com/problems/count-words-obtained-after-adding-a-letter/
 */
public class 统计追加字母可以获得的单词数 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.wordCount(new String[]{"ab", "a"}, new String[]{"abc", "abcd"}));
    }

    // TTL
    /*
class Solution {
    public int wordCount(String[] startWords, String[] targetWords) {
        Map<Integer, List<String>> lenToList = new HashMap<>();
        Map<String, int[]> stringToCount = new HashMap<>();
        for (String startWord : startWords) {
            int len = startWord.length();
            List<String> list;
            if (!lenToList.containsKey(len)) {
                list = new ArrayList<>();
                lenToList.put(len, list);
            } else {
                list = lenToList.get(len);
            }
            list.add(startWord);
            int[] count = new int[26];
            for (char c : startWord.toCharArray()) {
                count[c - 'a']++;
            }
            stringToCount.put(startWord, count);
        }
        int ans = 0;
        for (String targetWord : targetWords) {
            int len = targetWord.length();
            List<String> list = lenToList.get(len - 1);
            if (list == null) continue;
            int[] count = new int[26];
            for (char c : targetWord.toCharArray()) {
                count[c - 'a']++;
            }
            for (String startStr : list) {
                int[] curCount = stringToCount.get(startStr);
                int diffChar = -1;
                boolean ok = true;
                for (int i = 0; i < 26; i++) {
                    if (curCount[i] != count[i]) {
                        if (diffChar != -1) {
                            ok = false;
                            break;
                        } else {
                            diffChar = i;
                        }
                    }
                }
                if (ok) {
                    ans++;
                    System.out.println(startStr + "->" + targetWord);
                    break;
                }
            }
        }
        return ans;
    }
}
 */

    class Solution {
        public int wordCount(String[] startWords, String[] targetWords) {
            Map<Integer, Integer> map = new HashMap<>();
            // 统计所有targetWords的情况
            for (String targetWord : targetWords) {
                int c = code(targetWord);
                map.put(c, map.getOrDefault(c, 0) + 1);
            }
            int ans = 0;
            for (String startWord : startWords) {
                int c = code(startWord);
                for (int i = 0; i < 26; i++) {
                    // 模拟添加任意一位不存在的字符
                    int factor = 1 << i;
                    int search = factor | c;
                    // (factor & c) == 0 字符不存在
                    // map.containsKey(search) map中包含满足的target
                    if (((factor & c) == 0) && map.containsKey(search)) {
                        ans += map.get(search);
                        map.remove(search);
                    }
                }
            }
            return ans;
        }

        /**
         * 将字符串转换为整型
         * @param s
         * @return
         */
        private int code(String s) {
            int res = 0;
            for (char c : s.toCharArray()) {
                res |= (1 << (c - 'a'));
            }
            return res;
        }
    }

}
